package hah;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

public class NextGreaterElements {
    public int[] nextGreaterElements(int[] nums) {
            int[] res=new int[nums.length];
            for (int i=0;i< res.length;i++){
                int flag=0;
                for (int j=i+1;j!=i;j=(j+1)%res.length){
                    if (nums[j]>nums[i]){
                        flag=1;
                        res[i]=nums[j];
                        break;
                    }
                }
                if (flag==0){
                    res[i]=-1;
                }
            }
            return res;
    }

    //用单调栈解决！！
    public int[] nextGreaterElements2(int[] nums){
        int[] res=new int[nums.length];
        Arrays.fill(res,-1);
        Stack<Integer> s=new Stack<>();
        for (int i=0;i<2*nums.length;i++){
            while (!s.empty()&&nums[i]>nums[s.peek()]){
                res[s.pop()]=nums[i% nums.length];
            }
            s.push(i%nums.length);
        }
        return res;
    }

    //
    public int[] nextGreaterElement3(int[] nums1, int[] nums2) {
                int l=nums2.length;
                int[] ress=new int[nums1.length];
                HashMap<Integer,Integer> res=new HashMap<>();
                Stack<Integer> s=new Stack<>();
                for (int i=0;i<l;i++){
                    while(!s.empty()&&nums2[i]>s.peek()){
                        res.put(s.pop(),nums2[i]);
                    }
                    s.push(nums2[i]);
                }
                while(!s.empty()){
                    res.put(s.pop(),-1);
                }
                for (int i=0;i<nums1.length;i++){
                    ress[i]=res.get(nums1[i]);
                }
                return ress;
    }
}
